package com.ting.test.algorithms.递归和动态规划.从左往右的模型;

/**
 * 打印n层汉诺塔从最左边移动到最右边的全部过程
 */
public class 汉诺塔问题解法1 {
    public static void main(String[] args) {
        left2right(3);
    }



    private static void left2right(int n) {
        if (n == 1) {
            //如果是最后一层了，直接打印
            System.out.println("第1层从左边放到了右边");
            return;
        }
        //1.先将1~n-1层整体放到中间
        left2mid(n - 1);
        //2.将最后一层n放到右边，直接打印
        System.out.println("第" + n + "层从左边放到了右边");
        //3.将1~n-1层放到右边
        mid2right(n - 1);
    }

    private static void mid2right(int n) {
        if (n == 1) {
            //如果是最后一层了，直接打印
            System.out.println("第1层从中间放到了右边");
            return;

        }
        //1.先将1~n-1放到左边
        mid2left(n - 1);
        //2.将最后一层n放到右边
        System.out.println("第" + n + "层从中间放到了右边");
        //3,将1~n-1整体放到右边
        left2right(n - 1);

    }

    private static void mid2left(int n) {
        if (n == 1) {
            System.out.println("第1层从中间移动到左边");
            return;
        }
        //1 先将1~n-1从中间移动到右边
        mid2right(n - 1);
        //2.将最底层n从中间移动到左边
        System.out.println("第" + n + "层从中间移动到左边");
        //3.将1~n-1从右边移动到左边
        right2left(n - 1);

    }

    private static void right2left(int n) {
        if (n == 1) {
            System.out.println("第1层从右边移动到左边");
            return;
        }
        //先把1~n-1从右边移动到中间
        right2mid(n - 1);
        //将最底层n从右边移动到左边
        System.out.println("第" + n + "层从右边移动到左边");
        //3 1~n-1从中间移动到左边
        mid2left(n - 1);
    }

    private static void right2mid(int n) {
        if (n == 1) {
            System.out.println("第1层从右边移动到中间");
            return;
        }
        //1. 先把1~n-1从右边移动到左边
        right2left(n - 1);
        // 2.吧最后一次从右边移动到中间
        System.out.println("第" + n + "层从右边移动到中间");
        //3.吧n-1层从左边移动到右边
        left2right(n - 1);
    }

    private static void left2mid(int n) {
        if (n == 1) {
            System.out.println("第1层从左边移动到中间");
            return;
        }
        //1. 先把1~n-1从左边移动到右边
        left2right(n - 1);
        // 2.吧最后一次从左边移动到中间
        System.out.println("第" + n + "层从左边移动到中间");
        //3.吧n-1层从右边移动到中间
        right2mid(n - 1);
    }
}
